#include <iostream>
#include "LinkStack.h"
#include "LinkQueue.h"

#if 0
    int Partition(int *array, int start, int end)
    {
        int left = start;
        int right = end;
        int temp = array[left];

        while(left < right)
        {
            while(array[right] > temp && left < right)
                right--;
            if(left < right)
                array[left++] = array[right];
            while(array[left] < temp && left < right)
                left++;
            if(left < right)
                array[right--] = array[left];
        }
        array[left] = temp;
        return left;
    }

    // 快速排序的非递归版本
    void Fast_no_recur(int *a, int start, int end)
    {
        LinkStack s;
        // 把区间入栈
        s.Push(start);
        s.Push(end);

        while(s.IsEmpty() == false)
        {
            int right = s.GetTop();
            s.Pop();
            int left = s.GetTop();
            s.Pop();

            int mid = Partition(a, left, right);
            if(left < mid - 1)
            {
                // 入栈左区间
                s.Push(left);
                s.Push(mid - 1);
            }

            if(mid + 1 < right)
            {
                // 入栈右区间
                s.Push(mid + 1);
                s.Push(right);
            }
        }
    }
#endif

int main()
{
#if 0
    LinkStack s;
    for(int i = 0; i < 10; i++)
    {
        s.Push(i+1);
    }

    while(!s.IsEmpty())
    {
        std::cout<<s.GetTop()<<" ";
        s.Pop();
    }
    std::cout<<std::endl;
#endif

#if 1
    LinkStack s;

    int num = 0;
    int n = 0;
    std::cin>>num>>n;

    while(num > 0)
    {
        s.Push(num % n);
        num /= n;
    }
    
    while(s.IsEmpty() == false)
    {
        int a = s.GetTop();
        if(a >= 10)
            std::cout<<(char)(a - 10 + 'a');
        else
            std::cout<<a;
        s.Pop();
    }
    std::cout<<std::endl;
#endif

#if 0
    int a[] = {3, 5, 1, 2, 7, 4};

    Fast_no_recur(a, 0, sizeof(a) / sizeof(a[0]) - 1);

    for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
#endif

#if 0
    LinkQueue q;
    for(int i = 0; i < 10; i++)
    {
        q.Push(i+1);
    }
    
    while(q.IsEmpty() == false)
    {
        std::cout<<q.GetFront()<<" ";
        q.Pop();
    }
    std::cout<<std::endl;
    return 0;

#endif


    return 0;
}
